\documentclass[a4paper,10pt,brazil]{article}
\pagenumbering{arabic}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{latexsym}
\usepackage{indentfirst}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{graphics}
\usepackage{textcomp}
\usepackage{listings}
\usepackage{hyphenat}

\lstset{
frame=trbL,                 % adds a frame around the code
numbers=left,
breaklines=true,
basicstyle=\footnotesize,
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
tabsize=2,                  % sets default tabsize to 2 spaces
backgroundcolor=\color[rgb]{0.97,0.97,0.97},  % choose the background color. You must add \usepackage{color}
}
\usepackage{dinossauro}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23,5cm}
\evensidemargin 0cm
\oddsidemargin 0cm
\topmargin 0cm

\hyphenation{au-xi-li-a-res}


\begin{document}
\begin{titlepage}
\begin{center}
\MakeUppercase{\large Universidade Federal de Minas Gerais}\\[0.1cm]
\MakeUppercase{\large Insituto de Ciências Exatas}\\[0.1cm]
\MakeUppercase{\large Departamento de Ciência da Computação}\\[0.1cm]
\MakeUppercase{\large Redes Complexas}

\vfill
\textsc{\Large Trabalho Prático 1}\\[0.5cm]

\hrule \vspace{0.4cm}
{ \huge \bfseries Basic Network Analysis Techniques}\\[0.4cm]
\hrule \vspace{1.5cm}

{\large
{\bf Professor:} \\
Virgílio A. F. Almeida\\

\vfill

{\bf Alunos:}\\
Leonel Fonseca Ivo\\
Raphael O. S. M. de Faria\\[0.5cm]
{\tt \{leonelf,rapha\}@dcc.ufmg.br}
\vfill
 
\today}
\end{center}
 \thispagestyle{empty}
\end{titlepage}

\pagebreak

\tableofcontents
\newpage

\section{Introdução}

O presente trabalho tem como objetivo exercitar o uso de algumas técnicas básicas de análise de redes complexas. Para tal, será utilizada uma base de dados de tamanho moderado disponível no \textit{site} da Universidade Stanford.

A base de dados representa uma rede de coautorias de publicações científicas entre autores de artigos que foram submetidos à categoria de Teoria da Física de Alta Energia.

Para a implementação das técnicas, utilizou-se \textit{scripts} em \textit{shell} e, para facilitar o desenvolvimento deste trabalho, utilizou-se um controle de versão tendo o \textit{Google Code} como repositório. Todo o trabalho pode ser acessado pelo \textit{link} disponibilizado nas referências deste trabalho.

\section{Filtragem da Base de Dados}

  \subsection{Problemas e Inconsistências}

A partir de uma análise prévia da base de dados, verificou-se a necessidade de filtrar alguns problemas e inconsitências. São eles:

\begin{enumerate}
  \item Nomes de autores compostos apenas por caracteres numéricos ou caracteres especiais, tais como ``=.\"{} ' \`{}\{\}~()\_-?!*'';
  \item Autores com o mesmo nome, à exceção de um ou outro caractere especial. Um exemplo é: Bonn e Bonn);
  \item Autores cujo nome é composto por apenas uma letra ou autores com o nome do tipo ``Aa'';
  \item Autor com o nome ``De''. O problema com o nome desse autor era que seu no cálculo de seu grau era obtido um valor maior que o verdadeiro. Isso acontecia porque eram incluídas na contagem as ocorrências dos nomes que continham a palavra ``de'';
  \item Inconsistências no padrão de linha da base de dados, em que algumas linhas não possuem o formato especificado, não apresentando lista de autores para uma determinada publicação.
\end{enumerate}

  \subsection{Decisões Tomadas}

Para cada ressalva feita acima, tomou-se as seguintes decisões:

\begin{enumerate}
  \item Foram removidos todos os autores cujos nomes eram apenas numéricos ou compostos somente pelos caracteres especiais citados. Na maioria dos casos, os graus desses ``autores'' não eram relevantes;
  \item Todos os caracteres especiais e dígitos foram removidos dos nomes dos autores e, com isso, os autores cujos nomes se diferenciavam somente por alguns desses caracteres passaram a ser vistos como o mesmo autor;
  \item Esses autores foram mantidos, visto que tinham papel significativo;
  \item Esse autor foi removido, mesmo porque tinha grau nulo;
  \item Essas inconsistências não tiveram nenhum tratamento especial. O que acontece nesses casos é que, por exemplo, o nome de uma publicação será tratado como sendo o nome de um autor. Entretranto, como esse nome não aparecerá na colaboração de nenhum trabalho, seu grau será zero e, portanto, não terá interferência na resolução dos exercícios.
\end{enumerate}

O \textit{script} utilizado para fazer essas alterações está listado no apêndice deste documento.

\renewcommand{\labelenumi}{\textbf{\alph{enumi}}}

\section{Resolução dos Exercícios}

A listagem de todos os códigos-fonte utilizados na resolução dos problemas encontram-se no Apêndice desse documento.

\subsection{Exercício 1}

Para calcular o \emph{degree} de cada autor, foi criado um \textit{script} em \emph{shell} que necessita de dois arquivos auxiliares: uma com todos os nomes de autores, gravada no arquivo \emph{autores}; e outra com os autores de cada publicação, gravada no arquivo \emph{coautores}. Para a geração desta listas, também utilizamos comandos \emph{shell} do padrão \textbf{POSIX}.

Partes desses arquivos são mostradas abaixo.
\newline

\emph{autores}

\begin{codigoMargem}
A
Aa
Aarts
Abad
Abada
Abanov
Abarenkova
Abbaspur
Abdalla
AbdelKhalek
...
\end{codigoMargem}

\emph{coautores}

\begin{codigoMargem}
 Horne & Horowitz
 Mikovic
 Huitu & Nemeschansky
 Witten
 Intriligator
 Ooguri & Sasakura
 LeCLair & Smirnov
 Griffin
 Sen
 Lerche & Smit & Warner
...
\end{codigoMargem}


Para ambos os arquivos, utilizou-se o \textit{script} de filtragem da base de dados listado no apêndice A1, o qual faz os tratamentos discutidos na seção anterior além de gerar os arquivos. O arquivo de \textit{coautores} possui, em cada linha, os nomes dos autores de cada publicação separados por ``\&'', na ordem em que aparecem na base de dados. Já o arquivo de \textit{autores} possui um autor em cada linha, organizados em ordem alfabética.

Os gráficos foram gerados utilizando o \emph{gnuplot}.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio1_a.png}
\caption{Relação entre o número de autores por grau}
\end{figure}


\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio1_b.png}
\caption{Relação entre o número de autores por grau em escala logarítimica}
\end{figure}

\newpage
A partir dos gráficos obtidos, nota-se que essa base de dados segue a Lei de Potências, pois existem muitos nós com grau baixo e poucos nós com grau alto. O gráfico de escala logarítimica nos mostra a tendência de evolução da rede, em que um grupo seleto de autores possuem grande número de colaborações enquanto a maior parte deles possuem poucas colaborações.

\subsection{Exercício 2}

\begin{enumerate}
\item 

O número de nós existentes no grafo é o número de autores existentes na rede. Como a listagem dos autores já está armazenada no arquivo \textit{autores}, um autor por linha, pode-se obter o total de vértices do grafo com um comando simples de \textit{shell} que conta o número de linhas desse arquivo. Esse comando, juntamente com o resultado - número de vértices/autores da rede - é mostrado abaixo.

\begin{codigoMargem}
\$ cat autores | wc -l
5773
\end{codigoMargem}

Já para encontrar o maior componente conectado do grafo, utilizou-se a ferramenta de manipulação de grafos \textit{Pajek}. Para tal, essa ferramenta necessita de um arquivo de entrada em um formato específico (\emph{grafo.net}), o qual foi gerado pelo \textit{script} listado no apêndice A4. Parte desse arquivo é mostrado abaixo.

\begin{codigoMargem}
*Vertices 5773
1 A
2 Aa
3 Aarts
4 Abad
5 Abada
...
*edges
1 1 
1 128 
1 354 
1 1366
1 2260
...
\end{codigoMargem}

O arquivo de entrada para o \textit{Pajek} é dividido em duas partes: a primeira possiu o número total de vértices na primeira linha e a listagem dos vértices com seus respectivos identificadores nas linhas seguintes; a segunda parte, iniciada pela linha "*edges", apresenta a listagem das arestas existentes no grafo (na forma ``\emph{vertice1 vertice2}''). A primeira parte foi feita simplesmente copiando-se o arquivo \emph{autores} e acrescentando-se um identificador para cada autor. Já a segunda parte (\emph{grafo2.net}), de maior complexidade, foi gerada a partir do \textit{script exercicio2.sh}, listado no apêndice A4.

Uma vez criado o arquivo de entrada, utilizou-se o menu "Net/Components/WEAK" seguido de "Operations/Extract From Network/Partition", que resulta em um arquivo contendo a relação de cada vértice ao componente conectado a que ele pertence. Esse arquivo foi salvo no arquivo chamado \textit{componentes}, o qual contém o total de componentes conectados de cada tamanho (por exemplo, 139 componentes de 2 vértices). O arquivo completo é listado abaixo.

\lstinputlisting[caption=\emph{componentes}]{../dados/componentes}

Já tendo a relação entre cada vértice com seu componente conectado, o maior componente conectado foi descoberto com o  \textit{script} mostrado abaixo, que é parte do código do \textit{script} no apêndice A4.

\begin{codigoMargem}
\$(cat ../dados/componentes | cut -d " " -f1 | sort -nr | head -n 1)
4879
\end{codigoMargem}

O tamanho do maior componente conectado, dado como resposta a esse \textit{script}, é 4879. Como esse tamanho representa 84,5\% do tamanho do grafo, podemos dizer que essa rede apresenta um componente gigante.

\item A partir do arquivo \textit{componentes} gerado no item anterior, pode-se obter o número de componentes conectados de cada tamanho com o \textit{script} mostrado abaixo, o qual também faz parte do \textit{script} listado no apêndice A4.

\begin{codigoMargem}
\$ cat componentes  | sort -n | uniq -c  | tr -s " " | cut -d " " -f2 | \\sort -n | uniq -c  | awk '{print $2 " " $1}'
\end{codigoMargem}

O gráfico gerado é mostrado abaixo.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio2.png}
\caption{Relação entre o tamanho dos componentes conectados e a quantidade de componententes conectados, em escala logarítimica}
\end{figure}

O gráfico obtido segue novamente a Lei de Potências, demonstrando sua tendência de manter um componente gigante, uma vez que há uma maior probabilidade de que novos vértices tenham arestas ligando-os a outros vértices do maior componente conectado, visto que esse último já aglomera a maior parte dos vértices do grafo.

\newpage
\item Para este exercício, utilizou-se utilizar o \textit{Pajek} para fazer a busca em largura primeiro. Para tal, forneceu-se o arquivo \textit{grafo.net} como entrada para o programa e acionou-se a seguinte sequência de menus: Net -$>$ k-Neighboors -$>$ Input. Como resultado disso, o \textit{Pajek} gera um arquivo em que são listadas as distâncias de cada vértice para o vértice de origem.

O \textit{script exercicio2\_c.sh} faz algumas transformações no arquivo gerado pelo \textit{Pajek} a fim de gerar o gráfico mostrado abaixo.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/BFS.png}
\caption{Distâncias dos autores ao autor Ambjorn}
\end{figure}

Na geração desse gráfico verificou-se que, para os nós da rede que não pertencem ao componente conectado em que o \emph{Ambjorn} está inserido (que é o maior componente conectado da rede), a distância encontrada entre eles e \emph{Ambjorn} foi infinita. Isso está de acordo com o esperado porque, uma vez que os outros vértices não pertencem ao mesmo componente conectado, então não existem caminhos entre eles e o vértice em questão.

Analisando-se o gráfico em que considera-se somente os vértices pertencentes ao maior componente conectado, verifica-se a ocorr\^{e}ncia do Fen\^{o}meno do Mundo Pequeno nessa rede, pois a dist\^{a}ncia m\'{a}xima encontrada para o autor \emph{Ambjorn} foi 9 e, al\'{e}m disso, a maior parte dos demais v\'{e}rtices tem dist\^{a}ncia menor ou igual a 5 em relação ao v\'{e}rtice em quest\~{a}o. Pode-se notar que, at\'{e} que se atinja a dist\^{a}ncia 4, o n\'{u}mero de v\'{e}rtices aumenta à medida que a distância aumenta. A partir desse marco, o número de vértices diminui à medida que a distância aumenta.

Para esse componente, calculou-se também a distância média entre os vértices do maior componente conectado e o autor \emph{Ambjorn}, utilizando para isso o comando abaixo mostrado no \textit{script exercicio2\_c.sh}. O valor encontrado é mostrado abaixo.

\begin{codigoMargem}
3.98
\end{codigoMargem}

Esse valor comprova a ocorrência do fenômeno do mundo pequeno na rede em questão, uma vez que a distância média entre os autores do maior componente conectado ao autor \emph{Ambjorn} é bem baixa, aproximadamente 4 passos.

\end{enumerate}

\subsection{Exercício 3}

\begin{enumerate}
  \item Para encontrar o coeficiente de clusterização de cada autor da rede, foi necessário a criação de dois novos arquivos. O primeiro, chamado \emph{relacionados}, tem como objetivo listar os autores que colaboraram com cada determinado autor. O segundo, chamado \emph{clusterizacao}, lista o coeficiente de clusterização de cada vértice do grafo. Em seguida, são apresentadas partes desses arquivos.
\newline

\emph{relacionados}

\begin{codigoMargem}
Relacionados(1):  1  128  354  1366  2260  2390  3500  3809  3978  4162  5339 
Relacionados(2):  2  470  1827  4953 
Relacionados(3):  3  446  554  3567  4849  5509  5543 
Relacionados(4):  4  100  4300 
Relacionados(5):  5  595  1833  4796
...
\end{codigoMargem}

\emph{clusterizacao}

\begin{codigoMargem}
.22
1.00
.20
0
.66
1.00
1.00
1.00
.05
1.00
...
\end{codigoMargem}

Vale ressaltar que, para gerar o arquivo \textit{clusterizacao}, considerou-se que todos os vértices com grau 0 ou 1 tinham um coeficiente de clusterização de 1, uma vez que estão ``relacionados'' a eles mesmos ou a um único outro autor.

Tendo gerado o arquivo \textit{clusterizacao}, para encontrar o coeficiente médio basta somar todos os valores encontrados e dividir pelo número de vértices do grafo. O seguinte comando, que está incluso no arquivo \emph{script exercicio3.sh} listado no apêndice A5, é responsável por esse cálculo.

\begin{verbatim}
ccmedio=$(echo "scale=2; ($(cat ../dados/clusterizacao | tr '\n' '+' | 
sed 's/+\$//g')) / $(cat ../dados/autores | wc -l) " | bc)
\end{verbatim}

O resultado da execução do \emph{script exercicio3.sh} é mostrado abaixo, juntamente com o valor de coeficiente de clusterização médio do grafo.

\begin{codigoMargem}
\$ ./exercicio3.sh 
Coeficiente medio do grafo: .67
\end{codigoMargem}

  \item Para gerar as arestas dessa rede de forma aleatória, primeiro gera-se um vetor de \emph{d} posições, em que \emph{d} é o total de vértices do grafo. Cada posição do vetor armazena o valor do \textit{degree} do nó representado naquela posição. Por exemplo, na posição \emph{i} do vetor, o valor \textit{$x_{i}$} é o grau do vértice de identificador \emph{i}.

  Criado o vetor, esse último é percorrido de trás para frente gerando \emph{$y_{i}$} números aleatórios, sendo \emph{$y_{i}$} o grau do vértice \emph{i}, para cada elemento desse vetor. Cada um desses números aleatórios representam identificadores de outros vértices aos quais deseja-se conectar. Se os vértices representados por cada um desses números ainda puderem fazer alguma conexão, então faz-se a conexão e decrementa-se o grau de ambos os vértices. Repete-se isso até que tenha-se feito todas as \emph{$y_{i}$} ligações de cada vértice do grafo (ou seja, quando o valor do \textit{degree} do vértice sendo analisado chegar a zero).

  Foram utilizadas duas abordagens. Na primeira e mais simples delas, permitiu-se que um mesmo vértice fosse sorteado mais de uma vez dentre as relações de um determinado vértice. Essa abordagem não está correta, mas serve como efeito de comparação, dando como resultado um coeficiente médio de 0.5.

  Na segunda abordagem, impediu-se que um mesmo vértice fosse sorteado mais de uma vez dentre as relações de um determinado vértice. O resultado foi um coeficiente médio de 0.24, que é consideravelmente menor que o da rede original.

  A partir desses coeficientes médios de clusterização das redes aleatórias, consideravelmente menores que o da rede original, pode-se concluir que a evolução da rede de colaborações científicas não deve se dar de forma completamente aleatória, pois se fosse o caso os coeficientes médios de clusterização encontrados não teriam diferença tão significativa. Isso significa que deve haver algum tipo de mecanismo inerente a esse tipo de rede que faz com que ela evolua de forma não-aleatória. Dentre alguns possíveis mecanismos, podemos citar a amizade entre alguns autores, a localização geográfica e a área de atuação.

  Para a geração do gŕafico, concluiu-se que não fazia sentido gerar um gráfico com a distribuição de graus dos vértices de cada rede, sendo que essa distribuição é a mesma em ambas (como afirmado na primeira frase do enunciado deste exercício). Dessa forma, achou-se mais ilustrativo a geração de um gráfico que mostra a distribuição de coeficientes de clusterização entre os vértices de cada uma das duas redes (a rede original e a de arestas geradas aleatoriamente). Para a geração desse gráfico - um único arquivo com dois gráficos superpostos - utilizou-se os dois \textit{scripts} colocados abaixo, que geram os gráficos em separado, mais o código \emph{gnuplot} listado na sequência.

\begin{codigoMargem}
\$ cat ../dados/clusterizacao | sort -n  | uniq -c | awk '{print $2 " " $1}'  
> ../dados/clusterizacao.plot
\end{codigoMargem}

\begin{codigoMargem}
\$ cat ../dados/clusterizacao_aleatorio | sort -n  | uniq -c | 
awk '{print $2 " " $1}'  > ../dados/clusterizacao_aleatorio.plot
\end{codigoMargem}

\lstinputlisting[caption=Geração do gráfico de coeficientes de clusterização]{../src/exercicio_3.gnu}

O gráfico resultante é mostrado abaixo.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio3.png}
\caption{Distribuição dos coeficientes de clusterização nos grafos original e aleatório, em escala logarítimica}
\end{figure}

Esse gráfico evidencia o que foi constatado no cálculo do coeficiente médio para as duas redes. A rede original tende a ter coeficientes de clusterização mais elevados que os da rede aleatória, o que reforça a teoria de que existe algum tipo de mecanismo que faz com que a formação e evolução da rede de colaborações científicas seja não-aleatória.

\end{enumerate}


\subsection{Exercício 4}

  \begin{enumerate}
    \item Para esse exercício foi necessário gerar um arquivo contendo o número de autores em comum entre dois autores que formam uma aresta no grafo. Para cada autor no arquivo \textit{autores}, preenche-se um vetor de \textit{$n_{i}$} posições, sendo \textit{$n_{i}$} o grau do vértice \emph{i}, contendo cada um dos colaboradores de \emph{i}. Para cada um dos elementos desse vetor, verifica-se se existem coautores comuns ao vértice sendo analisado (a partir de consulta ao arquivo \emph{relacionados}), excluindo o próprio vértice. A contagem de coautores em comum para cada aresta é impressa no arquivo \emph{vertices\_relacionados}, segundo o formato ``\emph{coautores\_comuns vertice1 vertice2}''. Parte desse arquivo é mostrado abaixo.

\begin{codigoMargem}
3 1 128
2 1 354
2 1 1366
3 1 2260
3 1 2390
0 1 3500
1 1 3809
3 1 3978
2 1 4162
1 1 5339
...
\end{codigoMargem}

Gerado esse arquivo, sua ordenação é feita aplicando-se o comando mostrado a seguir, que ordena decrescentemente de acordo com a primeira coluna do arquivo. O código completo para a resolução desse exercício está listado no apêndice A6 deste documento.

\begin{codigoMargem}
cat ../dados/vertices_relacionados | sort +0 -1 -nr
\end{codigoMargem}

Tendo o arquivo ordenado dessa forma, o \textit{script exercicio4.sh} remove as arestas da seguinte forma: primeiro remove-se de 1\% em 1\% das arestas com maior valor de \emph{$w_{ij}$}, até que tenha-se removido 10\% do total de arestas; em seguida, continua-se removendo as arestas restantes de 10\% em 10\%, até que tenha-se removido todas.

Foram gerados dois gráficos para este exercício, um em escala linear e o outro na escala log-log, que são mostrados a seguir.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio4_a.png}
\caption{Redução do tamanho do maior componente conectado}
\end{figure}

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio4_a_log.png}
\caption{Redução do tamanho do maior componente conectado em escala logarítmica}
\end{figure}
\newpage
A partir da análise dos gráficos percebe-se que a remoção de arestas do grafo implica na redução do tamanho do componente conectado, como era de se esperar. Entretanto, percebe-se que essa redução é bastante pequena, como pode-se notar pela inclinação da primeira parte dos gráficos. Essa redução ocorre praticamente de forma linear enquanto a porcentagem de arestas removidas está abaixo de 60\%-70\%. Quando atinge-se essa quantidade de arestas removidas, a queda do tamanho do maior componente conectado é mais drástica, como percebe-se pela inclinação da segunda parte dos gráficos.

Esse comportamento aparentemente contraditório ocorre porque essas remoções causam uma diluição no maior componente conectado, até que chegue ao ponto em que removem-se arestas que mantém muitos vértices conectados ao componente. Isso porque, como remove-se primeiramente arestas cujos vértices possuem um maior número de vértices em comum, são removidas primeiramente as arestas internas aos componentes conectados, que os tornam mais densos. A remoção dessas arestas não é tão impactante no tamanho do componente conectado porque as arestas restantes (de menor número de vértices relacionados) mantém caminhos alternativos dentro do componente conectado, impedindo que grande parde dos seus vértices sejam desconectados. Em contrapartida, a partir do momento em que comeca-se a remover as arestas restantes, que mantinham os caminhos alternativos dentro do maior componente conectado, o tamanho desse último começa a diminuir drasticamente, pois já não haverão mais caminhos alternativos para manter muitos vértices conectados a esse componente. O esquema a seguir ilustra melhor esse comportamento.
\newpage
\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/grafos.png}
\caption{Esquema de diluição do gráfico}
\end{figure}

    \item Para a resolução deste exercício, o procedimento adotado foi semelhante ao do item anterior. Foi necessário criar um arquivo em que cada linha contém o número de publicações comuns a cada dois autores que formam uma aresta. O arquivo gerado foi denominado \emph{papers\_relacionados}, e uma parte dele é mostrada abaixo.

\begin{codigoMargem}
1 1 128
1 1 354
1 1 1366
1 1 2260
1 1 2390
1 1 3500
1 1 3809
1 1 3978
1 1 4162
1 1 5339
...
\end{codigoMargem}

As arestas do grafo são obtidas consultando-se o arquivo \textit{relacionados}, em que cada um dos identificadores em uma determinada linha são coautores do autor sendo representado naquela linha do arquivo. Como os autores nesse arquivo estão representados por seus identificadores, para obter o nome de cada coautor de um determinado autor faz-se uma busca por esse identificador no arquivo \textit{dicionario}, que possui a relação de nomes e ids. Essa busca pelo nome é feita pelo comando abaixo, também incluído no \textit{script exercicio4\_b.sh}, listado no apêndice A6 deste documento.

\begin{codigoMargem}
elementoNome=\$(grep -iw -m 1 "\${elemento}" dados/dicionario | cut -d" " -f2)
\end{codigoMargem}

Uma vez obtido o nome, faz-se uma busca no arquivo de \textit{coautores} pelas linhas que apresentam os dois nomes - o que significa que os dois colaboraram em uma mesma publicação - e conta-se a quantidade dessas ocorrências, o que representa o total de publicações em que os dois autores em questão participaram. Parte desse arquivo, ordenando decrescentemente em relação a \emph{$z_{ij}$}, é exibido abaixo.

\begin{codigoMargem}
33 2571 2868
31 2985 4083
30 942 4693
30 942 4554
30 942 4410
30 942 4360
30 942 4211
30 942 4132
30 942 4056
30 942 4001
...
\end{codigoMargem}

Tendo gerado esse arquivo, o \textit{script exercicio4\_b.sh} remove as arestas da mesma forma que foi feito no item anterior. O gráfico resultante é mostrado abaixo.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio4_b.png}
\caption{Redução do tamanho do maior componente conectado}
\end{figure}
\newpage
\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{../graficos/exercicio4_b_log.png}
\caption{Redução do tamanho do maior componente conectado em escala logarítmica}
\end{figure}

Analisando os gráficos acima, percebe-se que o comportamento é muito similar ao dos gráficos do item anterior.  Pode-se justificar este comportamento pelo fato de que nesta estratégia as primeiras arestas a serem removidas são aquelas que tem a menor probabilidade de influenciar os componentes conectados. Isso porque, quando dois autores possuem muitas publicações em comum, a tendencia é que muitas destas publicações envolvam também outros autores, o que significa que há mais chances de haverem outros caminhos entre esses autores. A diferença entre essa estratégia e a do item anterior é que esta é um pouco mais especulativa, uma vez que o fato de dois autores possuírem muitas publicações em comum não implica em eles terem muitos vizinhos relacionados (podem ser os únicos autores de todas ou da maioria das publicações comuns). No item anterior, quando dois autores possuem um grande número de vizinhos relacionados, certamente existem caminhos alternativos ligando-os que não passe pela aresta que os liga diretamente.

  \end{enumerate}


\section{Conclusão}

A implementação de algumas técnincas básicas de análise de redes proporcionou uma melhor compreensão do que foi estudado sobre elas e auxiliou, ainda, na visualização prática de alguns ``fenômenos'', como o Fenomêno do Mundo Pequeno e o encontrado no terceiro exercício (em que as redes aleatórias apresentam menores coeficientes de clusterização médios do que a rede original).

Mesmo com as dificuldades encontradas, principalmente no que se refere à eficiência dos programas escritos, pode-se dizer que o trabalho atendeu ao seu objetivo de expor os autores à algumas práticas comuns quando trabalha-se sobre esse tipo de bases de dados.


\newpage
\appendix

\lstset{language=bash,
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
%numbersep=5pt,                  % how far the line-numbers are from the code
%backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
%showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
%showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,	                % adds a frame around the code
tabsize=2,	                % sets default tabsize to 2 spaces
%captionpos=b,                   % sets the caption-position to bottom
%breaklines=true,                % sets automatic line breaking
%breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
%title=\lstname,                 % show the filename of files included with \lstinputlisting; also try caption instead of title
%escapeinside={\%*}{*)}          % if you want to add a comment within your code
extendedchars=true,
inputencoding=utf8
}

\section{Listagem dos \textit{scripts}}

  \subsection{Filtragem da Base de Dados}
\lstinputlisting[caption=filtra.sh]{../src/filtra.sh}

  \subsection{Geração de arquivos auxiliares}
\lstinputlisting[caption=autores.sh]{../src/autores.sh}

  \subsection{Exercício 1}
\lstinputlisting[caption=exercicio1.sh]{../src/exercicio1.sh}

  \subsection{Exercício 2}
\lstinputlisting[caption=exercicio2.sh]{../src/exercicio2.sh}
\lstinputlisting[caption=exercicio2\_c.sh]{../src/exercicio2_c.sh}

  \subsection{Exercício 3}
\lstinputlisting[caption=Primeiro item]{../src/exercicio3.sh}
\lstinputlisting[caption=Gera as arestas aleatórias]{../src/exercicio3_b.sh}
\lstinputlisting[caption=Calculo do coeficiente para o grafo aleatório]{../src/exercicio3_clusterizacao_aleatorio.sh}

  \subsection{Exercício 4}
\lstinputlisting[caption=exercicio4.sh]{../src/exercicio4.sh}
\lstinputlisting[caption=exercicio4\_b.sh]{../src/exercicio4_b.sh}

  \subsection{Geração de gráficos}
\lstinputlisting[caption=Exercicio 1 item 'a']{../src/exercicio_1_a.gnu}
\lstinputlisting[caption=Exercicio 1 item 'b']{../src/exercicio_1_b.gnu}
\lstinputlisting[caption=Exercicio 2]{../src/exercicio_2.gnu}
\lstinputlisting[caption=Exercicio 3]{../src/exercicio_3.gnu}
\lstinputlisting[caption=Exercicio 4]{../src/exercicio_4.gnu}

\nocite{*}
\bibliographystyle{plain}
%\bibliographystyle{apalike}
\renewcommand{\refname}{Referências}
\addcontentsline{toc}{section}{Referências}
\bibliography{referencias}

\end{document}
